package com.alexd.leetcode.contest.week101;

/*902. 最大为 N 的数字组合
用户通过次数 0
用户尝试次数 0
通过次数 0
提交次数 0
题目难度 Hard
我们有一组排序的数字 D，它是  {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）

现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。

返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。

 

示例 1：

输入：D = ["1","3","5","7"], N = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：

输入：D = ["1","4","9"], N = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。
 

提示：

D 是按排序顺序的数字 '1'-'9' 的子集。
1 <= N <= 10^9
*/
public class Solution3 {
	int[] dp = null;
	int[] floor = null;
	public int atMostNGivenDigitSet(String[] D, int N) {
        int DCnt = D.length;
        dp = new int[10];//dp[9]
        dp[1] = DCnt;//我们可以写 DCnt 个一位数字
        dp[2] = dp[1]*DCnt;
        for (int i = 2; i < dp.length; i++) {
			dp[i] = dp[i-1]*DCnt;
		}
        for (int i = 2; i < dp.length; i++) {
			dp[i] = dp[i-1]+dp[i];
		}
        
        floor = new int[10];//0-9
        for(String s:D) {
        	int i = Integer.parseInt(s);
        	for (int j = i; j < floor.length; j++) {
				floor[j] ++;
			}
        }
        
        int res = solve(N);
        
        return res;
    }
	public int solve(int N) {
		System.out.println("slove--"+N);
		if(N < 10) {
			System.out.println("solve "+N+" res="+floor[N]);
			return floor[N];
		}
		
		
		int head = N;
		int deep9 = 0;
		int num = 1;
		int floorCnt = 1;
		while(head > 9) {
			head = head/10;
			deep9++;
			num *= 10;
			floorCnt *= floor[9];
		}
		
		int fullLenNum = 1;//N的N位表示个数
		for(char c:Integer.toString(N).toCharArray()){
			fullLenNum *= floor[(c-'0')];
		}
		
		int res = 0;
		if(fullLenNum == 0) {
			res = dp[deep9];
		}else {
			if(floor[head-1] == floor[head]) {
				res = (floor[head-1] * floorCnt) + dp[deep9];
			}else {
				res = ((floor[head]-1) * floorCnt) + dp[deep9];
			}
			
		}
		
		/*int fullLenNum = 1;//N的N位表示个数
		for(char c:Integer.toString(N).toCharArray()){
			fullLenNum *= floor[(c-'0')];
		}
		
		
		if(fullLenNum == 0 ) {
			
		}
		else {
			res = fullLenNum  + dp[deep9];
		}*/
				
		
		System.out.println("solve "+N+" res="+res);
		return res;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/*
		 
		输入：D = ["1","4","9"], N = 1000000000
		输出：29523
		解释：
		我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
		81 个四位数字，243 个五位数字，729 个六位数字，
		2187 个七位数字，6561 个八位数字和 19683 个九位数字。
		总共，可以使用D中的数字写出 29523 个整数。
		
		输入：D = ["1","4","9"], N = 6234567891
		输出：?
		解释：
		floor(D[6]) * dp[9] + solve(234567891)
		
		*/

		String[] D = {"9"};
		if(1 == new Solution3().atMostNGivenDigitSet(D, 55)) {
			System.out.println("%######################testcase1 pass");
		}
		
		String[] D2 = {"5","6"};
		if(2 == new Solution3().atMostNGivenDigitSet(D2, 19)) {
			System.out.println("%######################testcase2 pass");
		}

			
		String[] D3 = {"1"};
		if(3 == new Solution3().atMostNGivenDigitSet(D3, 834)) {
			System.out.println("%######################testcase3 pass");
		}
		String[] D4 = {"1","3","5","7"};
		if(20 == new Solution3().atMostNGivenDigitSet(D4, 100)) {
			System.out.println("%######################testcase4 pass");
		}
		String[] D5 = {"1","4","9"};
		if(29523 == new Solution3().atMostNGivenDigitSet(D5, 1000000000)) {
			System.out.println("%######################testcase4 pass");
		}
		
		String[] D6 = {"3","4","5","6"};
		if(18 == new Solution3().atMostNGivenDigitSet(D6, 64)) { //4*3+2 + 4
			System.out.println("%######################testcase4 pass");
		}
		
		
			
	}

}
